package com.darrenchan.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-02-21 16:32
 */
public class Q17 {
    static Map<Character, String> map;

    static {
        map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
    }

    public List<String> letterCombinations(String digits) {
        List<String> results = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return results;
        }

        dfs(digits, 0, map, new ArrayList<String>(), results);
        return results;
    }

    private void dfs(String digits, int index, Map<Character, String> map, ArrayList<String> subsets, List<String> results) {
        if (index == digits.length()) {
            results.add(String.join("", subsets));
            return;
        }

        String res = map.get(digits.charAt(index));
        for (int i = 0; i < res.length(); i++) {
            subsets.add(res.charAt(i) + "");
            dfs(digits, index + 1, map, subsets, results);
            subsets.remove(subsets.size() - 1);
        }
    }
}
